public class demo67 {
   /* class Solution {
        private static int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};    // 移动方向，下右上左

        public int minTimeToReach(int[][] moveTime) {
            int n = moveTime.length, m = moveTime[0].length;
            Queue<int[]> pq = new PriorityQueue<>(
                    (a,b) -> a[0] - b[0]
            );                                                         // 优先队列, 存储到达每个位置的最早时间和单元格编号
            pq.offer(new int[]{0, 0});                                 // 初始将起点时间和id加入队列
            boolean[] visited = new boolean[n * m];                    // visited[i]表示编号为i的单元格是否访问
            visited[0] = true;                                         // 标记起始id已访问

            // BFS
            while(true){
                int[] info = pq.poll();        // 获取队首单元格信息
                int t = info[0], r = info[1] / m, c = info[1] % m;   // 当前队列中最早可达位置的信息
                if(r == n - 1 && c == m-1)return t;
                for(int[] direct: directions){
                    int nr = r + direct[0], nc = c + direct[1];                 // 移动到下一个单元格的坐标
                    int nid = nr * m + nc;                                      // 位置对应的id
                    if(nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nid]){
                        visited[nid] = true;                                               // 标记单元格已入队
                        pq.offer(new int[]{Math.max(t, moveTime[nr][nc]) + 2-(nr+nc)%2, nid});    // 单元格可以移动，加入队列；到达单元格的时间 = 最早可达时间 和 通过当前格子移动到达的时间的最大值
                    }
                }
            }
        }
    }*/

}
